1. Field of the Invention
This invention relates generally to the field of steganography. More particularly, the present invention relates to the field of digital watermark detecting methods and devices.
2. Description of the Related Art
The synergies between recently developed data compression techniques, high capacity storage media, the internet and other high bandwidth distribution channels have rendered digital media nearly ubiquitous. In view of these developments, technologies for the control of distribution, copying and identification of authorship and/or ownership of such media are gaining importance and relevance in the marketplace. In particular, the effective enforcement of copyrights in digital media is a complex problem, primarily due to the nature of the media itself. Indeed, unless preventative measures are taken, digital data is easily and perfectly reproducible, with no loss of fidelity.
So-called xe2x80x9cdigital watermarksxe2x80x9d have gained attention recently as one possible weapon in a content developer""s arsenal to combat piracy or unauthorized distribution or reproduction of digital media, such as video. In general, watermarks are a message, symbol or any distinctive marking that is transparently added to the video signal for the purpose of identifying whether the copy is an authorized one, the author of the video content, its distributor, owner or like information. The process of adding the distinctive message, symbol or marking to the digital media is generally referred to as the embedding process. Preferably, digital watermarks are embedded in the digital media (whether audio, still pictures or video) so as to render them invisible to the intended audience (such as, for example, moviegoers) and reliably detectable by appropriate detection systems. In general, visibility and detectability are directly related to one another: the more visible a watermark is, the more reliably it will be detected. Conversely, a well-concealed watermark may be difficult to reliably detect. An acceptable compromise between visibility and detectability, therefore, must typically be reached.
Several methods have been proposed to embed a watermark in a data stream. In the case of a video stream, for example, each video frame may be divided into a lattice of blocks of a given size. Each block, therefore, consists of a matrix of picture elements (hereafter, pixels), each having a number of characteristics associated therewith, such as luminance, chrominance etc. A transformation may be carried out on each block. For example, a Discrete Cosine Transform (hereafter, DCT), a Discrete Fourier Transform (hereafter, DFT) or some other transformation may be carried out on each block of each frame of the video stream. Such transformations generate information related to the spectral content of the video stream. Once this information is obtained, a watermark or a portion thereof may be embedded in one or more blocks by evaluating and selectively modifying the transformed block of pixels and then applying the inverse transform. For example, a watermark or a portion thereof may be embedded as directed perturbations of a single or a plurality of blocks. By selectively perturbing the pixels of a transformed block and thereafter applying an inverse transform, for example, a watermark may be embedded with low visibility. This is possible, because the human visual and auditory systems do not readily distinguish between small variations in spectral content, making it possible for video information of a given frequency to mask watermark data of the same or an adjacent frequency.
Watermarked video streams often are scaled to accommodate different formats. For example, movie theater screens generally have an approximate 16:9 aspect ratio, in that the movie theater screen is about 16 units long and 9 units wide. Television screens on the other hand have a 4:3 aspect ratio. Thus, video scaled for one format must often be scaled to another format. Video may be horizontally scaled and/or vertically scaled. FIG. 1 shows an example of the scaling of a block of watermarked video data. As shown in FIG. 1, a 16 by 16 (16xc3x9716) pixel watermarked block of video data may, for example, in DVD applications, be horizontally scaled by a factor of, for example, {fraction (4/3)}, the so-called Pan and Scan scaling. The scaled watermarked block then, has a vertical dimension of 16 pixels and a non-integral horizontal dimension of 16*{fraction (4/3)}, or {fraction (64/3)}.
Video is often cropped and shifted, for the same reasons as discussed above or for altogether different reasons incident to, for example, digital compression techniques and/or unauthorized manipulations of the video stream. For example, a watermark block may not start at the origin of the first video block because of, for example, one or more missing rows or columns. Such scaling, cropping and shifting render the detection of watermarks more complex. Indeed, a given video stream may have undergone some form of scaling and shifting, but the exact scale utilized and the amount of shift of the watermark block may not be known. However, the need to reliably detect the embedded watermarks remains.
What are needed, therefore, are devices and methods to detect watermarks embedded in video streams having undergone an unknown scaling among a predetermined and finite number of known scales. What are also needed are devices and methods to detect watermarks in video streams having undergone an arbitrary shift. What are also needed are devices and methods to detect watermarks in video streams having been scaled by an unknown scale factor and having been shifted by an unknown number of pixels. Also needed are devices and methods to reliably ascertain the scale and shift of a watermarked video stream.
It is, therefore, an object of the present invention to provide devices and methods to detect watermarks embedded in video streams having undergone an unknown scaling among a predetermined and finite number of known scales. Another object of the present invention is to provide devices and methods to detect watermarks in video streams having undergone an arbitrary shift. A further object of the present invention is to provide devices and methods to detect watermarks in video streams having been scaled by an unknown scale factor and having been shifted by an unknown number of pixels. In accordance with the above-described objects and those that will be mentioned and will become apparent below, an embodiment of a method of detecting a watermark in a watermarked video stream, the watermark having been scaled by an unknown scale among a predetermined finite number of scales, according to the present invention comprises, for each of the predetermined number of scales, the steps of:
dividing the video stream into a plurality of equally sized scaled watermark blocks;
reading the plurality of scaled watermark blocks into a plurality of read blocks;
accumulating each of the plurality of read blocks into one of a predetermined number of read block bins;
re-scaling each of the accumulated read blocks and combining the re-scaled accumulated read blocks into a single video accumulated block; and
evaluating a predetermined quantity within the video accumulated block.
According to further embodiments, the predetermined number of read block bins may be determined by each of the predetermined number of scales. The scaled watermark blocks may be of size N*(IH/JH)xc3x97N*(IV/JV), where an original watermark has a size of Nxc3x97N and where (IH/JH) and (IV/JV) are the reduced fractions of the horizontal and vertical scales, respectively, and the predetermined number of read block bins may be IH for each horizontal scale and IV for each vertical scale. The reading step may read read blocks of a same size for each of the predetermined number of scales. The evaluating step may include the step of transforming the video accumulated block corresponding to each of the predetermined number of scales into a frequency domain. The transforming step may include a step of applying a DCT to the video accumulated block corresponding to each of the predetermined number of scales. The predetermined quantity may include, for example, the power of a DCT and the evaluating step may include a step of selecting that DCT having the greatest power, the DCT having the greatest power pointing to a correct scale of the watermark among the predetermined number of scales and a correct shift of the watermark within the watermark blocks.
The present invention may also be viewed as a method of processing a scaled watermarked video stream, comprising the steps of:
reading watermarked blocks from the video stream in read blocks of equal size;
cyclically distributing successive read blocks into one of a predetermined number of read bins;
accumulating the read blocks in each of the read bins;
re-scaling and combining each of the accumulated read blocks into a video accumulated block; and
detecting at least a presence of a watermark in the video accumulated block.
The predetermined number of read bins may be related to the scale applied to the watermark blocks. The scale applied to the watermarked blocks may be expressed as I/J, where I and J are relatively prime and the distributing step may cyclically distribute the read blocks into I read bins. The distributing step, for each video scale of a predetermined number n of video scales of format In/Jn where In and Jn are relatively prime, may distribute every Inth read block in a same read bin among the predetermined number of read bins. The predetermined number of read bins may be In. The detecting step may include the step of applying a DFT or a DCT on the video accumulated block. The read bins may be memory spaces within a memory device and the distributing step may include a step of storing or accumulating the successive read blocks in the memory spaces. The read bins may each correspond to consistent pixel offsets of starts of read blocks relative to starts of the watermark blocks within the video stream. The detecting step may include the step of detecting a shift of the watermark within the watermark blocks. The reading, distributing, accumulating, re-scaling and combining and the detecting steps may be carried out for each suspected scale of a predetermined number of scales. A step of selecting one result of the detecting steps may also be carried out, the result pointing to a correct scale and shift of the watermark in the watermarked blocks.
According to another preferred embodiment, the present invention is a watermark detecting device to detect a watermark in a watermarked video stream, the watermark having been scaled by an unknown scale among a predetermined number of scales, comprising:
means for extracting from the video stream a plurality of equally sized scaled watermark blocks;
means for reading the plurality of scaled watermark blocks into a plurality of read blocks;
means for accumulating each of the plurality of read blocks into one of a predetermined number of read block bins;
means for re-scaling each of the accumulated read blocks and combining the re-scaled accumulated read blocks into a single video accumulated block; and
means for evaluating a predetermined quantity within the video accumulated block corresponding to each of the predetermined number of scales.
A still further embodiment of the present invention is a method of processing a watermarked video stream, comprising the steps of:
utilizing a fractional remainder upon division operation to compute a number of bins in which to distribute portions of the video stream; and
distributing selected portions of the video stream in selected ones of the computed number of bins.
The portions of the video stream may include watermark blocks. The utilizing step may apply the fractional remainder operation to each of a plurality of suspected scales of the watermarked video stream. The bins may include memory spaces of a memory device.